/*
 * Copyright (c) 2020 - present, Inspur Genersoft Co., Ltd.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package com.inspur.edp.lcm.metadata.common;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Stack;

/**邻接矩阵的图类
 * @author xusy
 *
 * @param <T>
 */
public class Graph<T> {

    public final static String ROOT_LABEL = "root_label";
    /**
     * 用来存储顶点
     * T做为标识，vertext作为实际的顶点
     */
    private final Map<String, Vertex<T>> vertexMap;

    /**
     * 图是否为有向图<br>
     * 如果是有向图，则为true
     */
    final boolean isDirect;

    /**
     * 图的构造函数
     * @param isDirect  图是否为有向图<br>
     * 如果是有向图，则为true
     */
    public Graph(boolean isDirect){
        vertexMap=new LinkedHashMap<>();
        this.isDirect=isDirect;
    }


    //下面与图的顶点相关

    /**
     * 返回图中的顶点个数
     * @return 图中的顶点个数
     */
    public int getVertexCount(){
        return vertexMap.size();
    }

    /** 
     * 返回图的顶点的迭代器
     * @return 顶点的迭代器
     */
    public Iterator<Vertex<T>> getVertexIterator(){
        return vertexMap.values().iterator();
    }

    /**
     * 在图中插入节点，节点的标识为label
     * @param label 插入节点标识
     * @return 如果图中不存在该节点，则插入，返回true<br>
     * 如果图中已经存在该节点，则更新权值，返回false
     */
    public boolean addVertex(String label){
        return addVertex(label, null);
    }

    /**
     * 在图中插入节点，节点的标识为label
     * @param label 插入节点标识
     * @return 如果图中不存在该节点，则插入，返回true<br>
     * 如果图中已经存在该节点，则更新权值，返回false
     */
    public boolean addVertex(String label, T content){
        Vertex<T> vertex=vertexMap.get(label);
        if(vertex!=null){
            //如果图中已经存在该节点，则返回false
            return false;
        }
        //如果图中不存在该节点，则插入，返回true
        vertex= new Vertex<>(label, content);
        vertexMap.put(label, vertex);
        return true;
    }

    /**
     * 根据标识label获取对应的节点
     * @param label 节点标识
     * @return 图中已存在的节点
     */
    public Vertex<T> getVertex(String label){
        return vertexMap.get(label);
    }

    /**
     * 在图中插入根节点，节点的标识为ROOT_LABEL
     * @param content 插入根节点的content
     * @return 如果图中不存在该节点，则插入，返回true<br>
     * 如果图中已经存在该节点，则更新权值，返回false
     */
    public boolean addRootVertex(T content){
        Vertex<T> vertex=vertexMap.get(ROOT_LABEL);
        if(vertex!=null){
            //如果图中已经存在该节点，则返回false
            return false;
        }
        //如果图中不存在该节点，则插入，返回true
        vertex= new Vertex<>(ROOT_LABEL, content);
        vertexMap.put(ROOT_LABEL, vertex);
        return true;
    }

    /**
     * 获取图中指定根节点
     * @return 图中已存在的节点
     */
    public Vertex<T> getRootVertex(){
        return getVertex(ROOT_LABEL);
    }

    //下面与图的边相关
    /**
     * 在图中加入一条边，如果isDirect为true，则为有向图，则<br>
     * 建立一条以begin作为标识的节点开始的边，以end作为标识的节点结束<br>
     * 如果isDirect为false，则为无向图，则<br>
     * 建立两条边，一条以begin开始，到end ，一条以end开始，到begin
     * @param begin 开始节点的标识
     * @param end 结束节点的标识
     * @return 如果没有对应的边，则加入对应的边，返回true<br>
     * 如果有对应的边，则返回false
     * 如果没有以begin或者end标识的顶点，则直接返回false
     */
    public boolean addEdge(String begin,String end) {
        Vertex<T> beginVertex=vertexMap.get(begin);
        Vertex<T> endVertex=vertexMap.get(end);
        if(beginVertex==null||endVertex==null){
            //如果没有以begin或者end标识的顶点，则直接返回false
            return false;
        }
        //有向图和无向图都要建立begin到end的边
        //如果顶点已经与endVertex连接，那么将会更新权值，result=false
        //如果顶点没有与endVertex相连，则互相连接，result=true
        boolean result=beginVertex.connect(endVertex);
        if(!isDirect){
            //如果不是有向图，则建立两条边,一条以end开始，到begin
            endVertex.connect(beginVertex);
        }
        return result;
    }

    /**在图中删除一条边，如果isDirect为true，则为有向图，则<br>
     * 删除一条以begin作为标识的节点开始的边，以end作为标识的节点结束<br>
     * 如果isDirect为false，则为无向图，则<br>
     * 删除两条边，一条以begin开始，到end ，一条以end开始，到begin
     * @param begin 开始节点的标识
     * @param end 结束节点的标识
     * @return 如果有对应的边，则删除对应的边，返回true<br>
     * 如果没有有对应的边，则直接返回false
     * 如果没有以begin或者end标识的顶点，则直接返回false
     */
    public boolean removeEdge(String begin,String end){
        Vertex<T> beginVertex=vertexMap.get(begin);
        Vertex<T> endVertex=vertexMap.get(end);
        if(beginVertex==null||endVertex==null){
            //如果没有以begin或者end标识的顶点，则直接返回false
            return false;
        }
        //有向图和无向图都要删除begin到end的边
        //如果顶点已经与endVertex连接，那么将会删除这条边，返回true
        //如果顶点没有与endVertex连接，则啥都不做，返回false
        boolean result=beginVertex.disconnect(endVertex);
        if(!isDirect){
            //如果不是有向图，则删除两条边,一条以end开始，到begin
            endVertex.disconnect(beginVertex);
        }
        return result;
    }

    //下面与拓扑排序相关

    /**
     * 返回一个出度为0（以该点出发的边数为0或者以该点出发的边的结束点都被访问过了），而且没有被访问过的顶点
     * @return 如果没有，则返回null
     */
    public Vertex<T> getNextTuopoVertex(){
        Vertex<T> vertex;
        Iterator<Vertex<T>> iterator=getVertexIterator();
        while(iterator.hasNext()){
            vertex=iterator.next();
            if((vertex.isNotVisited())&&(vertex.getUnvisitedVertex()==null)){
                //返回一个出度为0（以该点出发的边数为0或者以该点出发的边的结束点都被访问过了），而且没有被访问过的顶点
                return vertex;
            }
        }
        //如果没有，则返回null
        return null;
    }


    /**
     * 返回拓扑排序，返回的stack，第一个pop出的是第一个要做的顶点，最后一个是最后一个才能做的顶点
     * @return 拓扑排序，返回的stack
     */
    public Stack<Vertex<T>> getTopoSort(){
        Stack<Vertex<T>> stack=new Stack<>();
        Vertex<T> vertex;
        while(true){
            vertex = getNextTuopoVertex();
            if(vertex==null){
                //如果得不到下一个出度为0的节点，直接返回stack
                return stack;
            }
            //顶点入栈并被访问,遍历完成后,出栈就可以获得图的一个拓扑序列
            stack.push(vertex);
            vertex.visit();
        }
    }
}